package algorithm;

/**
 * 字符串匹配kmp算法
 * KMP
 */
public class KMP {



    /**
     * 原始字符串是否包含待匹配的字符串
     *
     * 原始的暴力匹配
     *
     * @param origin
     * @param str
     * @return
     */
    public int boomStr(String origin,String str){

        int sLen = origin.length();
        int pLen = str.length();

        int i = 0;
        int j = 0;
        while (i < sLen && j < pLen) {
            if (origin.charAt(i) == str.charAt(j)) {
                //①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++
                i++;
                j++;
             } else {
                //②如果失配（即S[i] != P[j]），令i = i - (j - 1)，j = 0
                i = i - j + 1;
                j = 0;
            }
        }
        //匹配成功，返回模式串p在文本串s中的位置，否则返回-1
        if (j == pLen) {
            return i - j;
        }
        return -1;
    }

    /**
     * kmp算法
     * @see https://www.cnblogs.com/yjiyjige/p/3263858.html
     * @return
     */
    public int KmpSearch(String origin, String match){

        int sLen = origin.length();
        int pLen = match.length();

        int i = 0;
        int j = 0;
        int[] next = getNext(match);
        while (i < sLen && j < pLen){
            //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
            if (j == -1 || origin.charAt(i) == match.charAt(j)) {
                i++;
                j++;
            } else {
                //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
                //next[j]即为j所对应的next值
                j = next[j];
            }
        }
        if (j == pLen){
            return i - j;
        }
        return -1;
    }

    /**
     * 获取下一步的数组
     *
     * @param ps
     * @return
     */
    public int[] getNext(String match) {

        // char[] p = match.toCharArray();
        int[] next = new int[match.length()];
        next[0] = -1;
        int j = 0;
        int k = -1;
        while (j < match.length() - 1) {
           if (k == -1 || match.charAt(j) == match.charAt(k)) {
               ++j;
               ++k;
               if ( match.charAt(j) == match.charAt(k)) { // 当两个字符相等时要跳过
                  next[j] = next[k];
               } else {
                  next[j] = k;
               }
           } else {
               k = next[k];
           }
        }
        return next;
    }


    public static void main(String[] args) {

        KMP kmp = new KMP();
        int idx =  kmp.boomStr("abcdjAhddd", "hd");
        System.out.println(idx);


        int idx2 =  kmp.KmpSearch("abcdjAhddd", "hd");
        System.out.println(idx2);
    }

}